package algorithms.que14;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

/**
 * @功能
 * @创建时间 2020/9/12
 */
public class E1d4d22 {
    public static void main(String[] args)
    {
        int[] a= In.readInts(args[0]);
        int keyIndex;
        for(int key=-1;key<=a.length;key++)
        {
            keyIndex=rank(a,key);
            StdOut.printf("key is:%d,keyIndex is:%d\n",key,keyIndex);
            StdOut.println("-------");
        }
    }

    public static int rank(int[] a,int key)
    {
        int fn1=1;
        int fn=1;
        while(fn<a.length)
        {
            fn=fn+fn1;
            fn1=fn-fn1;
        }
        //
        int lo=0;
        int hi=a.length-1;
        int mid;
        while(lo<=hi)
        {
            mid=lo+(fn-fn1)-1; //使mid可以为0
            StdOut.printf("lo=%d,hi=%d,fn=%d,fn1=%d,mid=%d\n",lo,hi,fn,fn1,mid);
            if(key<a[mid])
            {
                hi=mid-1;
                fn=fn-fn1;  //设置监听范围
                fn1=fn1-fn;
            }
            else if(key>a[mid])
            {
                lo=mid+1;
                fn1=fn-fn1;
                fn=fn-fn1;
            }
            else
                return mid;
        }//end while
        return -1;
    }//end rank
}
